跳到主要内容

算法基础 2

· 阅读需 4 分钟

https://oi-wiki.org/dp/knapsack/#完全背包

完全背包问题与 01 背包问题的区别在于每种物品的数量都是无限的，因此可以对每种物品的体积进行遍历，而不是仅考虑取或不取。

状态转移方程​

令 dp[i][j] 为只能选前i个物品时，容量为j的背包可以达到的最大价值。

则有状态转移方程：dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i])

其中 w[i] 和 v[i] 分别为第 i 个物品的重量和价值。

优化​

令 dp[j] 表示容量为 j 的背包可以达到的最大价值。则有状态转移方程：dp[j] = max(dp[j], dp[j-w[i]]+v[i])。这里的 w[i] 和 v[i] 分别为第 i 个物品的重量和价值。

这种优化方式可以将空间复杂度从O(nm)降低至O(m)，其中 n 为物品数量，m 为背包容量。

例题​

LeetCode 322​

https://leetcode.com/problems/coin-change/

题意：给定面额不同的硬币和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果不能凑成总金额，返回 -1。

令dp[i][j]表示前i个硬币凑成j元钱，所需最少的硬币个数，那么dp[len(coins)-1][amount]则为最后的解。状态转移方程为dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1)。

核心代码：

N = len(coins)
dp = [math.inf] * (amount + 1)
dp[0] = 0
for coin in coins:
    for j in range(coin, amount + 1):
        dp[j] = min(dp[j], dp[j - coin] + 1)
return dp[-1] if not math.isinf(dp[-1]) else -1

LeetCode 377​

https://leetcode.com/problems/combination-sum-iv/

题意：给定一个无重复元素的数组nums 和一个目标值 target ，求由数组中的元素组成和为 target 的组合的个数。每个元素可以被选取无限次。

令dp[i]表示由数组中的元素组成和为 i 的组合的个数，状态转移方程为dp[i] = \sum_{num \in nums} dp[i-num]，其中num为数组中的元素，i-num>=0。

核心代码：

dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
    for num in nums:
        if i - num >= 0:
            dp[i] += dp[i-num]
return dp[-1]

LeetCode 139​

https://leetcode.com/problems/word-break/

题意：给定一个字符串和一个单词字典，确定该字符串是否可以分割成一个或多个单词的空格分隔序列。

令dp[i]表示字符串s的前i个字符能否被空格分割成若干个单词，状态转移方程为dp[i] = OR_{word} dp[i-len(word)] AND s[i-len(word):i]==word。

核心代码：

N = len(s)
dp = [False] * (N + 1)
dp[0] = True
for i in range(1, N + 1):
    for word in wordDict:
        m = len(word)
        if i - m >= 0:
            dp[i] = dp[i] or (dp[i - m] and s[(i - m):i] == word)
        if dp[i]:
            break
return dp[-1]